#include<iostream>
#include<vector>
#include<string>
using namespace std;


//97.交错字符串
bool isInterleave(string s1, string s2, string s3){
    int m = s1.size(), n = s2.size();

    //预处理 下标0表示空串的情况
    s1 = " " + s1;
    s2 = " " + s2;

    //状态表示 dp[i][j]表示s1[1,i]区间的子串和s2[1,j]区间的子串能否拼成s3[1,i+j]区间的子串
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1,false));

    //初始化
    dp[0][0] = true;
    for (int i = 1; i <= m; i++){
        if (s1[i] == s3[i]){
            dp[i][0] == true;
        }
        else{
            break;
        }
    }
    for (int j = 1; j <= n; j++){
        if (s2[j] == s3[j]){
            dp[0][j] = true;
        }
        else{
            break;
        }
    }

    //填表
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            //状态表示 根据s3最后一个字符分两种情况，满足其中一种即可
            //不能用两个if语句判断
            dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j]) || (s2[j] == s3[i + j] && dp[i][j - 1]);
        }
    }

    //返回值
    return dp[m][n];
}

//712.两个字符串的最小ASCLL码删除和
int minimumDeleteSum(string s1, string s2){
    //正难则反思想 找两个字符串的最大ASCLL码和的公共子序列

    int m = s1.size(), n = s2.size();

    //状态表示 dp[i][j]表示s1区间[0,i]和s2区间[0,j]的所有子序列中，最大ASCLL码和的公共子序列
    //添加第一行，表示s1为空串的情况，添加第一列，表示s2为空串的情况
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    //填表
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            //状态转移方程
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if (s1[i - 1] == s2[j - 1]){
                dp[i][j] = max(dp[i - 1][j - 1] + s1[i-1], dp[i][j]);
            }
        }
    }

    //统计两个字符串总的ASCLL码和
    int sum = 0;
    for(auto ch : s1){
        sum += ch;
    }
    for(auto ch : s2){
        sum += ch;
    }

    //返回值，总的和减去两个最大和公共子序列就是需要最小删除的和
    return sum - 2 * dp[m][n];
}



//718.最长重复子数组
int findLength(vector<int>& nums1, vector<int>& nums2){
    int m = nums1.size(), n = nums2.size();

    //状态表示 dp[i][j]表示nums1以i位置为结尾和nums2以j位置为结尾的公共子数组中的，最长的公共子数组长度
    //初始化 添加第0行和第0列，表示两个数组为空数组的情况，初始值设置为0
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    //返回值 因为不确定最长的公共子数组以那两个位置为结尾，所以需要找到状态表中的最大值
    int ret = 0;
    //填表
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            if (nums1[i - 1] == nums2[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }

            ret = max(ret, dp[i][j]);
        }
    }

    return ret;
}

int main(){

    return 0;
}